﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace TestConsole
{
    class Permutation
    {
        int n;
        int[,] idx;

        // Индексы текущего наименьшего мобильного и следующего за ним
        int m, m2;

        public Permutation(int N)
        {
            n = N;
            idx = new int[n, 2];

            // Заполняем индексы в порядке возрастания
            // Направления направления "вправо" 1> 2> 3>
            while (N-- > 0) { idx[N, 0] = N; idx[N, 1] = 1; }
            InvalidateMobile();
        }

        // Поиск индекса наименьшего мобильного элемента
        private void InvalidateMobile()
        {
            m = m2 = -1;
            for (int i = 0; i < n; i++)
            {
                // Проверка на мобильность
                int i2 = i + idx[i, 1] * 2 - 1;
                if (i2 > -1 && i2 < n && idx[i, 0] < idx[i2, 0])
                {
                    // Сравнение по значению
                    if (m == -1 || idx[i, 0] < idx[m, 0])
                    {
                        m = i; m2 = i2;
                    }
                }
            }

            LastSwapIndex = m < m2 ? m : m2;
        }

        /// <summary>
        /// Вычисление следующей перестановки
        /// </summary>
        public bool Next()
        {
            // Если мобильных элементов нет - завершение алгоритма
            if (m == -1) return false;

            // Находим все элементы меньше текущего мобильного и меняем их направление
            for (int i = 0; i < n; i++)
            {
                if (idx[i, 0] < idx[m, 0])
                {
                    idx[i, 1] = 1 - idx[i, 1];
                }
            }

            // Меняем местами наименьший мобильный элемент и его соседа
            Swap(ref idx[m, 0], ref idx[m2, 0]);
            Swap(ref idx[m, 1], ref idx[m2, 1]);

            InvalidateMobile();
            return true;
        }

        /// <summary>
        /// Индекс пары элементов коотрые будет обменяны на следющей итерации
        /// </summary>
        public int LastSwapIndex { get; private set; }

        private void Swap(ref int a, ref int b)
        { a = b + 0 * (b = a); }

        /// <summary>
        /// Возвращает элеметы массива в порядке перестановки
        /// </summary>
        public IEnumerable<T> Apply<T>(T[] Array)
        {
            for (int i = 0; i < n; i++)
            {
                yield return Array[idx[i, 0]];
            }
        }

        public static IEnumerable<Permutation> AllOf(int N)
        {
            Permutation p = new Permutation(N);
            do yield return p;
            while (p.Next());
        }
    }

    static class Task
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Введите количество цифр в перестановке");
            int n = Convert.ToInt32(Console.ReadLine());

            // Создайте один раз массив, который будете переставлять
            int[] A = new int[n];
            for (int i = 0; i < n; i++) A[i] = i + 1;

            // Перебирайте все перестановки
            foreach (var p in Permutation.AllOf(n))
            {
                // Применяйте каждую к Вашему массиву (получая копию исходного массива с переставленными элементами)
                var a = p.Apply(A).ToArray();

                // Выводите на экран
                for (int i = 0; i < n; i++)
                {
                    Console.Write(a[i]);
                    // Ставя точку в том месте где будет совершен следующий обмен
                    if (i == p.LastSwapIndex) Console.Write("");
                }
                Console.WriteLine();
            }
            Console.ReadLine();
        }
    }
}